Search for: All records

For graphs of average degree $$d$$, positive integer weights bounded by $$W$$, and accuracy parameter $$\epsilon>0$$, [Chazelle, Rubinfeld, Trevisan; SICOMP'05] have shown that the weight of the minimum spanning tree can be $$(1+\epsilon)$$-approximated in $$\tilde{O}(Wd/\epsilon^2)$$ expected time. This algorithm is frequently taught in courses on sublinear time algorithms. However, the $$\tilde{O}(Wd/\epsilon^2)$$-time variant requires an involved analysis, leading to simpler but much slower variations being taught instead. Here we present an alternative that is not only simpler to analyze, but also improves the number of queries, getting closer to the nearly-matching information theoretic lower bound. In addition to estimating the weight of the MST, our algorithm is also a perfect sampler for sampling uniformly at random an edge of the MST. At the core of our result is the insight that halting Prim's algorithm after an expected $$\tilde{O}(d)$$ number of steps, then returning the highest weighted edge of the tree, results in sampling an edge of the MST uniformly at random. Via repeated trials and averaging the results, this immediately implies an algorithm for estimating the weight of the MST. Since our algorithm is based on Prim's, it naturally works for non-integer weighted graphs as well.